import java.util.HashMap;
import java.util.Map;

public class Seven {

    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * @param preorder
     * @param inorder
     * @return
     */
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i=0;i<preorder.length;i++){
            map.put(preorder[i],i);
        }

       return BuildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);


    }

    public TreeNode BuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
        if (preorder_left>preorder_right)
            return null;
        int preorder_root = preorder_left;
        int inorder_root = map.get(preorder[preorder_root]);
        TreeNode root = new TreeNode(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;
        root.left = BuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);
        root.right = BuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);
        return root;

    }
}
